package com.zhaopin.theswordreferstooffer;

/**
 * @author yin.peide
 * @date 2021-06-28 10:17
 * 面试题38：数字在排序数组中出现的次数
 * 数据结构和算法pdf中：
 * 421，在排序数组中查找元素的第一个和最后一个位置-对二分法查
 * 找的改造
 */
public class Offer38 {
    public static void main(String[] args) {
        int[] attr = {1, 2, 3, 3, 3, 3, 4, 5};
        System.out.println(getFirstIndex(attr,3, 0, attr.length - 1));
    }

    public static int getFirstIndex(int[] data,int k, int start, int end) {
        {
            if (start > end) {
                return -1;
            }

            int middleIndex = (start + end) / 2;
            int middleData = data[middleIndex];

            if (middleData == k) {
                if ((middleIndex > 0 && data[middleIndex - 1] != k)
                        || middleIndex == 0) {
                    return middleIndex;
                } else {
                    end = middleIndex - 1;
                }

            } else if (middleData > k) {
                end = middleIndex - 1;
            } else {
                start = middleIndex + 1;
            }
            return getFirstIndex(data, k, start, end);
        }
    }

    //同理找last的结果//TODO 后期自己写
}
